package a.codetop;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _5三数之和 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>(); int n = nums.length;
        Arrays.sort(nums);
        int FIR = -99999;
        for (int i = 0; i <= n - 3; i++) {//要足够3个数
            int fir = i, l = i + 1, r = n - 1;

            //重的只算第一个
            if (nums[fir] == FIR)continue;
            FIR = nums[fir];

            while (l < r) {
                int L = nums[l], R = nums[r], sum3 = FIR + L + R;
                if (sum3 == 0) {
                    res.add(Arrays.asList(new Integer[]{FIR, L, R}));
                    //走到不同即可 (不要管同的让w去干活
                    while (l < n && nums[l] == L) l++;
                    while (r >= i && nums[r] == R) r--;
                } else if (sum3 < 0) {
                    while (l < n && nums[l] == L) l++;
                } else if (sum3 > 0) {
                    while (r >= i && nums[r] == R) r--;
                }
            }
        }
        return res;
    }
}
